package leetcode101.data_structure;

/**
 * @author Synhard
 * @version 1.0
 * @class Code17
 * @description 304. 二维区域和检索 - 矩阵不可变
 * 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 * 示例：
 *
 * 给定 matrix = [
 *   [3, 0, 1, 4, 2],
 *   [5, 6, 3, 2, 1],
 *   [1, 2, 0, 1, 5],
 *   [4, 1, 0, 1, 7],
 *   [1, 0, 3, 0, 5]
 * ]
 *
 * sumRegion(2, 1, 4, 3) -> 8
 * sumRegion(1, 1, 2, 2) -> 11
 * sumRegion(1, 2, 2, 4) -> 12
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-15 10:44
 */
public class Code17 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {3, 0, 1, 4, 2},
                {5, 6, 3, 2, 1},
                {1, 2, 0, 1, 5},
                {4, 1, 0, 1, 7},
                {1, 0, 3, 0, 5}
        };

        NumMatrix numMatrix = new NumMatrix(matrix);
    }

    static class NumMatrix {

        int[][] matrix;
        int[][] prefix;

        public NumMatrix(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            this.matrix = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                System.arraycopy(matrix[i], 0, this.matrix[i + 1], 1, n);
            }
            countPrefix();
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            if (row1 == row2 && col1 == col2) {
                return this.matrix[row1 + 1][col2 + 1];
            }
            return this.prefix[row2 + 1][col2 + 1] - this.prefix[row1][col2 + 1] - (this.prefix[row2 + 1][col1] - this.prefix[row1][col1]);
        }

        private void countPrefix() {
            int m = this.matrix.length;
            int n = this.matrix[0].length;
            this.prefix = new int[m][n];
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    int sum = 0;
                    for (int k = 0; k < i + 1; k++) {
                        sum += this.matrix[k][j];
                    }
                    this.prefix[i][j] = this.prefix[i][j - 1] + sum;
                }
            }
        }
    }
}

/*
二维矩阵的前缀和
 */